# -*- coding: utf-8 -*-

"""
    http://projecteuler.net/problem=25
    
    PROBLEM
    
    The Fibonacci sequence is defined by the recurrence relation:

    Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

    Hence the first 12 terms will be:

    F1 = 1
    F2 = 1
    F3 = 2
    F4 = 3
    F5 = 5
    F6 = 8
    F7 = 13
    F8 = 21
    F9 = 34
    F10 = 55
    F11 = 89
    F12 = 144

    The 12th term, F12, is the first term to contain three digits.

    What is the first term in the Fibonacci sequence to contain 1000 digits?

    
    NOTES
        
    
    REFERENCES
    
    
    PERFORMANCE
    time <function solution at 0x7f77fcfe2848>: 0.062908 s
    
"""
#
# Import
#
import time


#
# Globals / Constants
#
def timeit(f):
    def timer():
        t0 = time.time()
        returned = f()
        print "time %s: %.6f s" % (f, time.time() - t0)
        return returned
    return timer

def assert_match(value, expected, message=""):
    f = "value %s != expected %s"
    f = message != '' and f + " (%s)" or f + "%s"
    assert value == expected, f % (value, expected, message)


#
# Test Case / Solution
#
@timeit    
def test_case():
    assert_match(fib_digit(3), 12)
    print "test case passed!"

@timeit
def solution():
    return fib_digit(1000)

#
# Solution Code
#            
def fib_digit(ordinal):
    g = fib_digit_generator()
    digit_len = 0
    n = 0
    
    while digit_len != ordinal:
        n += 1
        number = g.next()
        digit_len = len(number)
        
    return n

def fib_digit_generator():
    n, n1, n2 = 0, 1, 1
    while True:
        yield str(n1)
        n, n1, n2 = n1, n2, n1+n2 


#
# Additional Tests
#


#
# Main
#
if __name__ == '__main__':
    test_case()
    print solution()
    